GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Postsches Korrespondenzproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Postsches Korrespondenzproblem</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Das Postsche Korrespondenzproblem (nach <a href="Emil_Leon_Post" title="Emil Leon Post">Emil Leon Post</a>, abgekürzt auch PKP oder englisch PCP) ist ein Beispiel für ein <a href="Entscheidbar" class="mw-redirect" title="Entscheidbar">unentscheidbares</a> <a href="Problem" title="Problem">Problem</a> in der <a href="Theoretische_Informatik" title="Theoretische Informatik">Theoretischen Informatik</a>.

Es wird häufig verwendet, um mittels <a href="Reduktion_(Theoretische_Informatik)" class="mw-redirect" title="Reduktion (Theoretische Informatik)">Reduktion</a> die Unentscheidbarkeit anderer Probleme zu zeigen.

Gegeben ist eine endliche Folge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> von Paaren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left((x_{1},y_{1}),(x_{2},y_{2}),\ldots ,(x_{m},y_{m})\right)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left((x_{1},y_{1}),(x_{2},y_{2}),\ldots ,(x_{m},y_{m})\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/25af7694ab373002b585db7ecbc1d2bdff59d2cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.525ex; height:2.843ex;" alt="{\displaystyle \left((x_{1},y_{1}),(x_{2},y_{2}),\ldots ,(x_{m},y_{m})\right)}" loading="lazy"> von nicht-leeren Wörtern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},x_{2},\ldots ,x_{m},y_{1},y_{2},\ldots ,y_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},x_{2},\ldots ,x_{m},y_{1},y_{2},\ldots ,y_{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7dab4e90755a0f426a65c7177a24944b70687971.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:28.432ex; height:2.009ex;" alt="{\displaystyle x_{1},x_{2},\ldots ,x_{m},y_{1},y_{2},\ldots ,y_{m}}" loading="lazy"> über einem endlichen Alphabet. Man nennt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> auch einen Problemfall oder eine Instanz.

Eine nicht-leere Folge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I=i_{1},i_{2},\ldots ,i_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I=i_{1},i_{2},\ldots ,i_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f0dfb87e3f392e667798327c40e09eb109c298f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.217ex; height:2.509ex;" alt="{\displaystyle I=i_{1},i_{2},\ldots ,i_{n}}" loading="lazy"> von Indizes aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,2,\ldots ,m\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1,2,\ldots ,m\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/977f1deaf1c5c37fb48c6e8786538316dcd43c7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.902ex; height:2.843ex;" alt="{\displaystyle \{1,2,\ldots ,m\}}" loading="lazy"> heißt eine Lösung zum Problemfall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">, falls die <a href="Konkatenation_(Wort)" class="mw-redirect" title="Konkatenation (Wort)">Konkatenation</a> (Verkettung) der Wörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{n}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4490ecf65630686b64a482f8d51bfbe12746b77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.228ex; height:2.343ex;" alt="{\displaystyle x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{n}}}" loading="lazy"> gleich der Konkatenation der Wörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i_{1}},y_{i_{2}},\ldots ,y_{i_{n}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i_{1}},y_{i_{2}},\ldots ,y_{i_{n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da85f1012ceff9a2350fb48bfbb72003d9b71b2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.657ex; height:2.343ex;" alt="{\displaystyle y_{i_{1}},y_{i_{2}},\ldots ,y_{i_{n}}}" loading="lazy"> ist.

Das Korrespondenzproblem ist dann die Aufgabe, zu einem beliebigen Problemfall anzugeben, ob er eine Lösung besitzt oder nicht. Das Korrespondenzproblem ist <a href="Entscheidbar" class="mw-redirect" title="Entscheidbar">unentscheidbar</a>, das heißt, es gibt keinen Algorithmus, der zu jedem beliebigen Problemfall die richtige Antwort gibt.

<div class="mw-heading mw-heading2"><h2 id="Anschauliche_Darstellung">Anschauliche Darstellung</h2></div>

Die Wortpaare <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{i},y_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{i},y_{i})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d6dbb919b91ccacf17ed47898048428a1baf9703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.912ex; height:2.843ex;" alt="{\displaystyle (x_{i},y_{i})}" loading="lazy"> eines Problemfalls kann man sich gut wie Dominosteine vorstellen, bei denen auf der einen Hälfte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> und auf der anderen Hälfte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"> steht. Es gibt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> Arten von Dominosteinen und von jeder Art stehen beliebig viele Dominosteine zur Verfügung.

Das Korrespondenzproblem lässt sich nun also wie folgt verstehen: Gibt es eine Folge von Dominosteinen, so dass die Wörter auf der oberen Hälfte der Dominosteine (von links nach rechts gelesen) dasselbe Wort ergeben wie die (von links nach rechts gelesenen) Wörter aus der unteren Hälfte der zusammengelegten Dominosteine?

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Gegeben:

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}=\left((1,101),(10,00),(011,11)\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e98cef4296623cd1cc237312928a17cd5bddf8b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.164ex; height:2.843ex;" alt="{\displaystyle P_{1}=\left((1,101),(10,00),(011,11)\right)}" loading="lazy">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{1}=1\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa02168f9e3d85c3f1f4665652e0e9b2a4b3c51c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.292ex; height:2.509ex;" alt="{\displaystyle \left.x_{1}=1\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.x_{2}=10\right.,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{2}=10\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1fb7af36d5d258d05dc1a624d9c6e648a869ca54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.454ex; height:2.509ex;" alt="{\displaystyle \left.x_{2}=10\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.x_{3}=011\right.}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{3}=011\right.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91df5b889a8b17f600942a9f0c32572c1efa30d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.97ex; height:2.509ex;" alt="{\displaystyle \left.x_{3}=011\right.}" loading="lazy">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{1}=101\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5175d6b4a2e88196934f6c2c13ccc016673d20e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.426ex; height:2.509ex;" alt="{\displaystyle \left.y_{1}=101\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.y_{2}=00\right.,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{2}=00\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b963bcdf57e13068720e4e2bd3ffa6a605a8ce18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.264ex; height:2.509ex;" alt="{\displaystyle \left.y_{2}=00\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.y_{3}=11\right.}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{3}=11\right.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65699afbf8d8e835c7a91bf11007fc7eb5c8f348.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.617ex; height:2.509ex;" alt="{\displaystyle \left.y_{3}=11\right.}" loading="lazy">

Lösung:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{1}=(1,3,2,3)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ccfbddfec2e01bdf49a9ceaa41cd46eb733d7a28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.737ex; height:2.843ex;" alt="{\displaystyle I_{1}=(1,3,2,3)}" loading="lazy">

Es gilt: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}\cdot x_{3}\cdot x_{2}\cdot x_{3}=1\cdot 011\cdot 10\cdot 011=101110011=101\cdot 11\cdot 00\cdot 11=y_{1}\cdot y_{3}\cdot y_{2}\cdot y_{3}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}\cdot x_{3}\cdot x_{2}\cdot x_{3}=1\cdot 011\cdot 10\cdot 011=101110011=101\cdot 11\cdot 00\cdot 11=y_{1}\cdot y_{3}\cdot y_{2}\cdot y_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/77d194b62637dd5b95cc93ad782641b4a28227a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:82.239ex; height:2.509ex;" alt="{\displaystyle x_{1}\cdot x_{3}\cdot x_{2}\cdot x_{3}=1\cdot 011\cdot 10\cdot 011=101110011=101\cdot 11\cdot 00\cdot 11=y_{1}\cdot y_{3}\cdot y_{2}\cdot y_{3}}" loading="lazy">.

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03f18d041b2df30adef07164dbf285878893dedc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.077ex; height:2.509ex;" alt="{\displaystyle I_{1}}" loading="lazy"> ist also eine Lösung des Problemfalls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/398f438d75434e6fbf48dc232c1ad7228a738568.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{1}}" loading="lazy">.

Als Dominofolge: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{101}}\ {\frac {011}{11}}\ {\frac {10}{00}}\ {\frac {011}{11}}}">

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{101}}\ {\frac {011}{11}}\ {\frac {10}{00}}\ {\frac {011}{11}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6cd35198d4d62d315587ec985bf92ab3398fdbad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:17.873ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{101}}\ {\frac {011}{11}}\ {\frac {10}{00}}\ {\frac {011}{11}}}" loading="lazy">.

Bemerkungen dazu:

Natürlich bildet jede Verkettung zweier Lösungen oder einer Lösung mit sich selbst wieder eine Lösung. Man kann also fragen, ob eine Lösung aus kürzeren Lösungen zusammengesetzt ist.

Die Lösung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1,3,2,3)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1,3,2,3)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fc3e122e93b22c9707b90c910828c38c7dece24b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.561ex; height:2.843ex;" alt="{\displaystyle (1,3,2,3)}" loading="lazy"> ist nicht aus kürzeren Lösungen zusammengesetzt: sie ist primitiv.

Manchmal gibt es mehrere primitive Lösungen, nicht jedoch in diesem Beispiel.

Das Beispiel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/398f438d75434e6fbf48dc232c1ad7228a738568.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{1}}" loading="lazy"> erweckt vielleicht den Eindruck, dass das Postsche Korrespondenzproblem gar nicht so schwierig ist. Es gibt jedoch auch Problemfälle, die nur sehr lange Lösungen haben.

Hierzu ein Beispiel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87858df7457aa93caaef5a316db87a7240cc8c29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{2}}" loading="lazy">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{1}=001\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1b8924fe7f549428fbe4634711d1e5cf825de5da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.617ex; height:2.509ex;" alt="{\displaystyle \left.x_{1}=001\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.x_{2}=01\right.,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{2}=01\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/36b11664f1c6e63915a45f8fb96c038d95d7f4e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.454ex; height:2.509ex;" alt="{\displaystyle \left.x_{2}=01\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.x_{3}=01\right.,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{3}=01\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd515a2dff2d6f372f8e52c122b8cbfeb73b03d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.454ex; height:2.509ex;" alt="{\displaystyle \left.x_{3}=01\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.x_{4}=10\right.}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.x_{4}=10\right.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f0e968bc8749cba7681f481db037a1b10bd8220.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.807ex; height:2.509ex;" alt="{\displaystyle \left.x_{4}=10\right.}" loading="lazy">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{1}=0\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0112b0ec34850850abd3549a2c2dbef58360a0a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.101ex; height:2.509ex;" alt="{\displaystyle \left.y_{1}=0\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.y_{2}=011\right.,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{2}=011\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ea82fd8e0ab87f37ab63c0de4b8cec9873f000e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.426ex; height:2.509ex;" alt="{\displaystyle \left.y_{2}=011\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.y_{3}=101\right.,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{3}=101\right.,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/37cd1aaaafa489437e587492729d5bea9c4be3e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.426ex; height:2.509ex;" alt="{\displaystyle \left.y_{3}=101\right.,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left.y_{4}=001\right.}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left.y_{4}=001\right.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c2e08341e038e2e51daeb3719a1bd9f844f742d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.779ex; height:2.509ex;" alt="{\displaystyle \left.y_{4}=001\right.}" loading="lazy">

Eine kürzeste Lösung besteht schon aus 66 Paaren:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{1}=(2,4,3,4,4,2,1,2,4,3,4,3,4,4,3,4,4,2,1,4,4,2,1,3,4,1,1,3,4,4,4,2,1,2,1,1,1,3,4,3,4,1,2,1,4,4,2,1,4,1,1,3,4,1,1,3,1,1,3,1,2,1,4,1,1,3)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5070f754000b5f16dcbb4544b06fabb0325e698d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:150.913ex; height:2.843ex;" alt="{\displaystyle I_{1}=(2,4,3,4,4,2,1,2,4,3,4,3,4,4,3,4,4,2,1,4,4,2,1,3,4,1,1,3,4,4,4,2,1,2,1,1,1,3,4,3,4,1,2,1,4,4,2,1,4,1,1,3,4,1,1,3,1,1,3,1,2,1,4,1,1,3)}" loading="lazy">

An dieser Lösung kann man leicht die Komplexität des Problems erkennen.

<div class="mw-heading mw-heading2"><h2 id="Grenzen_zwischen_Entscheidbarkeit_und_Unentscheidbarkeit">Grenzen zwischen Entscheidbarkeit und Unentscheidbarkeit</h2></div>

Durch systematisches Ausprobieren lässt sich eine Lösung nach endlicher Zeit finden, sofern es eine gibt. Das PKP ist somit ein <a href="Semi-entscheidbar" class="mw-redirect" title="Semi-entscheidbar">semi-entscheidbares</a> Problem.

Wenn es jedoch keine Lösung gibt, wird dieser Algorithmus nicht <a href="Terminiertheit" title="Terminiertheit">terminieren</a>. Der Nachweis, dass es kein Entscheidungsverfahren für PKP gibt, kann durch eine Reduktion des <a href="Halteproblem" title="Halteproblem">Halteproblems</a> auf eine Variante des Korrespondenzproblems erbracht werden.

<div class="mw-heading mw-heading3"><h3 id="Sonderfälle">Sonderfälle</h3></div>

Durch Einschränkung des Alphabets wird das Problem „einfacher“.

Lässt man nur Wortpaare über einem einelementigen Alphabet zu, dann wird aus dem PKP ein entscheidbares Problem. Das PKP eingeschränkt auf ein zweielementiges Alphabet dagegen bleibt unentscheidbar, denn ein beliebiges Alphabet kann in einem zweielementigen Alphabet kodiert werden.

Man kann auch die Größe einschränken, das heißt die Anzahl der Paare in den Problemfällen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">. Für die Größen 1 und 2 wird das PKP entscheidbar.<a href="#cite_note-1">[1]</a> Die Größe 5 reicht aus für Unentscheidbarkeit.<a href="#cite_note-Neary-2">[2]</a> Ob für die Größe 3 oder 4 das PKP entscheidbar ist oder nicht, ist noch ungeklärt.

Außerdem gilt: Wenn in allen Paaren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}=\left(x_{i},y_{i}\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}=\left(x_{i},y_{i}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6a32847217bb45cb67d0860d5d0730622fcd1fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:12.068ex; height:2.843ex;" alt="{\displaystyle p_{i}=\left(x_{i},y_{i}\right)}" loading="lazy"> die erste Komponente länger bzw. kürzer als die zweite ist (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall i\colon \left|x_{i}\right|>\left|y_{i}\right|}">

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\colon \left|x_{i}\right|>\left|y_{i}\right|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9028224dc56bf6d57a08f01cbfde62c65073b65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.883ex; height:2.843ex;" alt="{\displaystyle \forall i\colon \left|x_{i}\right|>\left|y_{i}\right|}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall i\colon \left|x_{i}\right|<\left|y_{i}\right|}">

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\colon \left|x_{i}\right|<\left|y_{i}\right|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e115cd2babb1ef780d3997917572561d121ba812.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.883ex; height:2.843ex;" alt="{\displaystyle \forall i\colon \left|x_{i}\right|<\left|y_{i}\right|}" loading="lazy">), ist die Instanz unlösbar. Dasselbe gilt, wenn ein Symbol nur in den ersten oder nur in den zweiten Komponenten vorkommt oder wenn es kein Paar gibt, das „gleich beginnt“ oder „gleich endet“ (<a href="Wort_(Theoretische_Informatik)#Präfix" class="mw-redirect" title="Wort (Theoretische Informatik)">Präfixe</a>, <a href="Wort_(Theoretische_Informatik)#Suffix" class="mw-redirect" title="Wort (Theoretische Informatik)">Suffixe</a>).

<div class="mw-heading mw-heading2"><h2 id="Trivia">Trivia</h2></div>

Nach einer Idee von Steffen Lange im Jahr 2011 kann das Postsche Korrespondenzproblem als Ausgangspunkt für eine <a href="Domino" title="Domino">dominoartige</a> Spiele-Familie, die sogenannten PCP-Spiele, dienen.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Wang-Parkettierung" title="Wang-Parkettierung">Wang-Parkettierung</a><a href="#cite_note-Neary-2">[2]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> <a href="Andrzej_Ehrenfeucht" title="Andrzej Ehrenfeucht">Andrzej Ehrenfeucht</a>, G. Rozenberg: <cite style="font-style:italic">On the (Generalized) Post Correspondence Problem with Lists of Length 2</cite>. In: <cite style="font-style:italic">Proc. 8th Int. Coll. Automata, Languages, and Programming</cite>. LNCS 115. Springer, 1981, S. 219–234.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Postsches+Korrespondenzproblem&rft.atitle=On+the+%28Generalized%29+Post+Correspondence+Problem+with+Lists+of+Length+2&rft.au=Andrzej+Ehrenfeucht%2C+G.+Rozenberg&rft.btitle=Proc.+8th+Int.+Coll.+Automata%2C+Languages%2C+and+Programming&rft.date=1981&rft.genre=book&rft.pages=219-234&rft.pub=Springer&rft.volume=LNCS+115" style="display:none">

</li>

<li id="cite_note-Neary-2">↑ <a href="#cite_ref-Neary_2-0">a</a> <a href="#cite_ref-Neary_2-1">b</a> Turlough Neary: <cite style="font-style:italic">Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words</cite>. In: <cite style="font-style:italic">32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)</cite> (= <cite style="font-style:italic">Leibniz International Proceedings in Informatics (LIPIcs)</cite>). Band 30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany 2015, ISBN 978-3-939897-78-1, S. 649–661, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230/LIPIcs.STACS.2015.649">10.4230/LIPIcs.STACS.2015.649</a> (<a rel="nofollow" class="external text" href="https://drops.dagstuhl.de/opus/volltexte/2015/4948/">dagstuhl.de</a> [abgerufen am 18. Februar 2019]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Postsches+Korrespondenzproblem&rft.atitle=Undecidability+in+Binary+Tag+Systems+and+the+Post+Correspondence+Problem+for+Five+Pairs+of+Words&rft.au=Turlough+Neary&rft.btitle=32nd+International+Symposium+on+Theoretical+Aspects+of+Computer+Science+%28STACS+2015%29&rft.date=2015&rft.doi=10.4230%2FLIPIcs.STACS.2015.649&rft.genre=book&rft.isbn=9783939897781&rft.pages=649-661&rft.place=Dagstuhl%2C+Germany&rft.pub=Schloss+Dagstuhl-Leibniz-Zentrum+fuer+Informatik&rft.series=Leibniz+International+Proceedings+in+Informatics+%28LIPIcs%29&rft.volume=30" style="display:none">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> <a href="Klaus_Peter_Jantke" title="Klaus Peter Jantke">Klaus Peter Jantke</a>: <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/297212574_PCP-Spiele">PCP-Spiele</a>, 2016, Technical Report KiMeRe-2012-04, Abteilung Kindermedien des <a href="Fraunhofer-Institut_f%C3%BCr_Digitale_Medientechnologie" title="Fraunhofer-Institut für Digitale Medientechnologie">Fraunhofer-Institut für Digitale Medientechnologie</a> IDMT

</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://jamesvanboxtel.com/projects/pcp-solver/">Online-PCP Lösungstool</a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-06-06" href="https://de.wikipedia.org/wiki/?title=Postsches_Korrespondenzproblem&oldid=256738956">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>